package sorting;

import java.util.Arrays;
import java.util.Random;

public class ShellSort {
	int[] a;
	int size;

	void insert(int k, int h) {
		int j;
		while ((j = k - h) >= 0) {
			if (a[j] <= a[k])
				break;
			int temp = a[j];
			a[j] = a[k];
			a[k] = temp;
			k = j;
		}
	}

	void sort() {
		int h;
		for (h = 1; h < size; h = h * 3 + 1)
			;
		while (h >= 1) {
			h /= 3;
			for (int i = h; i < size; i++) {
				insert(i, h);
			}

		}
	}
	public static void main(String[] args) {
		int size = 5;
		Random rand = new Random();
		int[] a = new int[size];
		for (int i = 0; i < size; i++)
			a[i] = rand.nextInt(20);		
		ShellSort ss = new ShellSort();
		ss.a = a;
		ss.size = size;
		System.out.println(Arrays.toString(a));
		ss.sort();
		System.out.println(Arrays.toString(a));
	}
}
